//
//  main.c
//  折半查找
//
//  Created by szcq on 2021/4/22.
//

#include <stdio.h>
#include <time.h>

int for_method(int nums[],int length,int keyValue);

int while_1_method(int nums[],int length,int keyValue);

int while_2_method(int nums[], int length, int key);

int main(int argc, const char * argv[]) {
    int values[50000] = {23,45,55,88,93,[49999] = 187};
    //找出  int value = 87 的  对应的索引值
    int keyValue = 187;
    int length = sizeof(values)/sizeof(values[0]);
    clock_t startTime = clock();
//    int index = for_method(values, length, keyValue);
    
    int index = while_1_method(values, length, keyValue);
//    int index = while_2_method(values, length, keyValue);


    clock_t endTime = clock();
    printf("消耗%lu毫秒\n", endTime - startTime);
    printf("索引值为 ** %d\n",index);
    return 0;
}

int while_2_method(int nums[], int length, int key)
{
    int min, max, mid;
    min = 0;
    max = length - 1;
    // 只要在范围内就需要查找
    while (min <= max) {
        // 计算中间值
        mid = (min  + max) / 2;
        if (key > nums[mid]) {
            min = mid + 1;
        } else if (key < nums[mid]) {
            max = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}


int while_1_method(int nums[],int length,int keyValue) {
    int min, max, mid;
    min = 0;
    max = length - 1;
    mid = (min + max) / 2;
    
    while (keyValue != nums[mid]) {
        if (keyValue > nums[mid]) {
            min = mid + 1;
        } else {
            max = mid - 1;
        }
        
        if (min > max) {
            return -1;//超出范围了
        }
        mid = (min + max) / 2;
    }
    return mid;
}


/// for 循环
int for_method(int nums[],int length,int keyValue) {
    for (int i = 0; i < length; i++) {
        if (keyValue == nums[i]) {
            return i;
        }
    }
    return -1;
}
